Origami [思维题]

Nowcoder 字节跳动冬令营网络赛 B

一道思维题，结果成了这次网络赛我唯一做出来的一道题。。。不过这次比赛抽奖抽中了三个T-shirt，emmmm，RP++。

分析

题目给出了长度为\(n\)，分为\(n\)段的一个纸带，并且从左到右按顺序每段都标有一个编号。要求对这个纸带进行多次折叠，使得纸带只有一段。此时，纸带从上向下读，可以得到一个\(n\)的排列。现在题目给出一个排列，问是否可以折叠出该排列。

很明显，这个题目应该从折叠的性质入手。刚开始的时候我认为可以将排列分为两部分进行还原，但发现不可行。后来认为是和逆序对有关，但是也很快就推翻了自己的想法。那么究竟该从何处着手呢？

我们不妨从“纸带”本身来考虑。一个标了数字的折叠的纸带，其与一串排列最大的不同是什么？不同的数字之间有纸带相连。也就是说，\(i\)永远会与\(i-1\)和\(i+1\)相连。那么，我们可以将所有的数连起来，若是不同的连线之间有重叠的话，则肯定折不出当前的情况。

那么我们如何实现这种“连线”和“交叉”的判断呢？首先，我们可以将需要连的线分为左右两部分。很明显，小的奇数到大的偶数的连线为一部分，而小的偶数到大的奇数的连线会是另一部分。所以，我们对这两个部分分开考虑即可。

那么，我们的问题便变成了判断几条线之间是否有交叉的问题了。实际上，它还可以被简化成括号表达式是否合法的问题-即括号（连线）之间只能包含，不能交叉。如此，我们便可以用栈来实现这个功能了。譬如，连线的两个数互为左右括号，若是他们在栈中相邻，则可取出消去。若是栈最后有数无法消去（除去那些本来就没有和其他点连线的数），则当前排列不能由纸带折叠而出。

代码

#include <iostream>
#include <algorithm>
#include <stack>

using namespace std;

stack<int> s1, s2;

int main()
{
    int T;
    cin >> T;

    while (T--)
    {
        while (!s1.empty())
            s1.pop();
        while (!s2.empty())
            s2.pop();

        int n;
        cin >> n;

        for (int i = 1; i<=n; i++)
        {
            int x;
            cin >> x;


            if ( !s1.empty() && max(s1.top(), x) % 2 == 0 && abs(s1.top()-x)==1 )
                s1.pop();
            else if ( !(n%2==1 && x==n) )
                s1.push(x);
            
            if ( !s2.empty() && (s2.top() ^ x) == 1)
                s2.pop();
            else if ( !(x==1 || (n%2==0 && n==x)))
                s2.push(x);

        }

        if (s1.size()!=0 || s2.size()!=0)
            cout << "No" << endl;
        else cout << "Yes" << endl;
    }
}

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。